HW#5 --- last modified February 06 2019 04:20:47..

Solution set.

Due date: May 11

Files to be submitted:
  Project.zip

Purpose: To gain experience with NP-completeness proofs and approximation algorithms.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO6 -- Given a problem determine within NP that is promised to be either in P or NP-complete prove which

LO7 -- Analyze or code an approximation algorithm for a optimization problem whose decision problem is NP-complete.

Specification:

This homeworks consists of the following written problems, together with a programming exercise described below. Submit the written problems in Hw5.pdf as part of your Hw5.zip file. Submit your code in this ZIP file as well.

1. Show the problem of whether the maximum independent set of a graph `G` has size `k` is `NP`-hard.
2. A `k`-coloring of a graph is `G=(V,E)` is a map from `f: V -> {1, ..., k}` such that if `(i,j) in G` then `f(i) ne f(j)`. Show that the language consisting of encodings of graphs which are 2-colorable is in `P`.
3. Prove that the language consistent of pairs `(langle G rangle, k)` where `G` is a graph and `k` is a positive integer such that `G` is `k` colorable is `NP`-complete.

For the coding part of the assignment I would like you to code the approximate vertex cover algorithm discussed in class and submit this in a file ApproxVertexCover.java as part of your HW5.zip file. This program will be compiled from the command line with the syntax:

javac ApproxVertexCover.java

It will then be run with a line like:

java ApproxVertexCover some_file_with_graph.txt

Here some_file_with_graph.txt will be a file containing the adjacency matrix for a graph. For example,

0 1 0 0 0 0 0
1 0 1 0 0 0 0
0 1 0 1 1 0 0
0 0 1 0 1 1 1
0 0 1 1 0 1 0
0 0 0 1 1 0 0
0 0 0 1 0 0 0 

which corresponds to the graph of Figure 35.1 in the book. On such an input, your program should run the approximate vertex cover algorithm we has and output the vertices in the cover it finds. The edge it should pick in the line pick an arbitrary edge should be chosen uniformly at random from the edgeset `E'`. It should print out the edges chosen. One possible output of the algorithm on the above graph is:

Edges Chosen:
(1,2)
(4,5)
(3,6)
Cover Found:
1 2 3 4 5 6

I would like you to test your program on a variety of graph for which you hand calculate the optimal vertex cover and see how this algorithm does versus the optimal. Write up your results in experiments.txt.

Point Breakdown